//
//  MapGraph.h
//  DiceWar
//
//  Created by xiaofeng on 20/6/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#ifndef CLASS_GAME_GAMEPLAY_MAPGRAPH_H_
#define CLASS_GAME_GAMEPLAY_MAPGRAPH_H_

#include "StaticMatrix.h"
#include "HexMapGrid.h"
#include "Player.h"
#include <deque>

class MapGraph
{
public:
    MapGraph();
    ~MapGraph();
    
public:
    typedef StaticMatrix<HexMapGrid, gameConstants::kHexMapSizeX, gameConstants::kHexMapSizeY> HexMapGridMatrix;
    typedef HexMapGridMatrix::const_iterator MapMatrixConstIter;
    typedef StaticMatrix<bool, gameConstants::kHexMapSizeX, gameConstants::kHexMapSizeY> TraverseMatrix;

    void init(const HexMapGridMatrix* pHexMapGridMatrix);
    
    /** test to see if the graph has only a single piece
     */
    bool isGraphSinglePiece() const;
    
    /** get the size of the biggest
     */
    int getLargestPieceSizeForPlayer(PlayerType type) const;
    
private:
    /** do a bfs on the map, start from the point specified with rootX, rootY
     return the number of traversed node in the search
     */ 
    int breadthFirstSearchOnMap(int rootX, int rootY, const HexMapGridMatrix* pHexMapGridMatrix, TraverseMatrix& traverseMatrix) const;

    /** do a bfs on the cells of a certain player, start from the point specified with rootX, rootY
     return the number of traversed node in the search
     */
    int breadthFirstSearchOnPlayerCells(int rootX, int rootY, PlayerType player, const HexMapGridMatrix* pHexMapGridMatrix, TraverseMatrix& traverseMatrix) const;

    /** to get the coordinate of the first available cell in the hex map 
     */
    bool getFirstAvailableCellOnMap(int& coordinateX, int& coordinateY) const;
    
    /** to get the coordinate of the first player's cell in the hex map 
     */
    void getFirstPlayerCellOnMap(int& coordinateX, int& coordinateY) const;
    
    /** to return the total number of cells for player to use in the map
     */
    int getNumAvailableCells() const;
    
    /** get the first node in the map that is not traversed and comply with the condition
     */
    template<typename CONDITION>
    HexCellCoordinate getRoot(const HexMapGridMatrix* pMapGrid, const TraverseMatrix& traverseMatrix, CONDITION condition) const;
    
    /** to do a bfs on the map based on the condition variable
     */
    template<typename CONDITION> 
    int bfs(int rootX, int rootY, TraverseMatrix& traverseMatrix, CONDITION condition) const;
    
private:
    const HexMapGridMatrix* m_pHexMapGridMatrix;
};

/** get the first node in the map that is not traversed and comply with the condition
 */
template<typename CONDITION>
HexCellCoordinate MapGraph::getRoot(const HexMapGridMatrix* pMapGridMatrix, const TraverseMatrix& traverseMatrix, CONDITION condition) const
{
    CCAssert(pMapGridMatrix, "Invalid Parameter");
    if (!pMapGridMatrix) return HexCellCoordinate(-1, -1);
    
    for (int xIndex = 0; xIndex < pMapGridMatrix->getSizeX(); xIndex++)
    {
        for (int yIndex = 0; yIndex < pMapGridMatrix->getSizeY(); yIndex++)
        {
            if (traverseMatrix(xIndex, yIndex)) continue;
            if (!condition(xIndex, yIndex)) continue;
            return HexCellCoordinate(xIndex, yIndex);
        }
    }
    
    return HexCellCoordinate(-1, -1);
}

template<typename CONDITION> 
int MapGraph::bfs(int rootX, int rootY, TraverseMatrix& traverseMatrix, CONDITION condition) const
{
    CCAssert(!traverseMatrix(rootX, rootY), "Invalid Root Node");
    if (traverseMatrix(rootX, rootY)) return 0;
    
    CCAssert(condition(rootX, rootY), "Invalid Root Node");
    if (!condition(rootX, rootY)) return 0;
        
    int numNodesTraversed = 0;
    
    std::deque<HexCellCoordinate> traverseQueue;
    traverseQueue.push_back(HexCellCoordinate(rootX, rootY));
    traverseMatrix(rootX, rootY) = true;
    numNodesTraversed++;
    CCLOG("NUM = %d, RootX = %d, RootY = %d", numNodesTraversed, rootX, rootY);
    
    while (!traverseQueue.empty())
    {
        HexCellCoordinate cell = traverseQueue.front();
        traverseQueue.pop_front();
        
        std::vector<HexCellCoordinate> neighbors;
        cell.getAllNeighbors(neighbors);
        
        for (std::vector<HexCellCoordinate>::const_iterator iter = neighbors.begin(); iter != neighbors.end(); ++iter)
        {
            const int kCoordinateX = iter->getX();
            const int kCoordinateY = iter->getY();
      
            if (!condition(kCoordinateX, kCoordinateY)) continue;
            if (traverseMatrix(kCoordinateX, kCoordinateY)) continue;
            
            traverseQueue.push_back(*iter);
            traverseMatrix(kCoordinateX, kCoordinateY) = true;
            numNodesTraversed++;
            CCLOG("NUM = %d, X = %d, Y = %d", numNodesTraversed, kCoordinateX, kCoordinateY);
        }
    }
    
    return numNodesTraversed;
}

#endif
